package com.mojito.learn.algorithm.common;

import java.util.Arrays;

/**
 * 十大排序算法
 *
 * <a href="https://mp.weixin.qq.com/s/aLeId4UmZBtvFAglOGsLAQ"></a>
 *
 * @author liufq
 * @since 2021-02-25 22:32:29
 */
public class SortAlgorithm {

    /**
     * 1. 冒泡排序：
     */
    public void bubbleSort(int[] data) {
        for (int i = 0; i < data.length - 1; i++) {
            for (int j = 0; j < data.length - 1 - i; j++) {
                if (data[j] > data[j + 1]) {
                    swap(data, j, j + 1);
                }
            }
        }
    }

    /**
     * 2. 选择排序：和冒泡类似，区别在于不用每次都交换，找到最大值记录位置，一次交换
     */
    public void selectionSort(int[] data) {
        // 总共要经过 N-1 轮比较
        for (int i = 0; i < data.length - 1; i++) {
            int min = i;

            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < data.length; j++) {
                if (data[j] < data[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }

            // 将找到的最小值和i位置所在的值进行交换
            if (i != min) {
                swap(data, i, min);
            }
        }
    }

    /**
     * 3. 插入排序：每次认为第一个有序，然后循环把后面的数据插入有序位置，通过不断跟有序数据比较交换实现
     * 优点：对基本有序的数据效率高
     */
    public void insertSort(int[] data) {
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < data.length; i++) {
            // 记录要插入的数据
            int tmp = data[i];

            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < data[j - 1]) {
                data[j] = data[j - 1];
                j--;
            }

            // 存在比其小的数，插入
            if (j != i) {
                data[j] = tmp;
            }
        }
    }

    /**
     * 4. 希尔排序
     */
    public void shellSort(int[] data) {
        int gap = 1;
        while (gap < data.length) {
            gap = gap * 3 + 1;
        }

        while (gap > 0) {
            for (int i = gap; i < data.length; i++) {
                int tmp = data[i];
                int j = i - gap;
                while (j >= 0 && data[j] > tmp) {
                    data[j + gap] = data[j];
                    j -= gap;
                }
                data[j + gap] = tmp;
            }
            gap = (int) Math.floor(gap / 3);
        }
    }

    /**
     * 5. 归并排序
     */
    public int[] mergeSort(int[] data) {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(data, data.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(mergeSort(left), mergeSort(right));
    }

    private int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }

    private int partition(int[] arr, int left, int right) {
        // 基准值：每一趟排序的目的就是把基准值放到一个位置，使得它的左边的值都比它小，右边的值都比它大，一般把第一个值作为基准值
        // 返回的就是这个位置，这个位置把数组拆成 2 段，每段再递归执行相同逻辑
        int pivot = left;
        // 基准值要放的位置，这个位置应该等于比基准值小的数的个数
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                // 找到比基准值小的数据后，交换当前数据和基准值位置数据
                swap(arr, i, index);
                // 每找到一个比基准值小的数据，基准值要放的位置就加 1
                index++;
            }
        }
        // 最后把基准值放到找到的位置
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    /**
     * 快速排序
     */
    public int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

//    public void quickSort(int[] data, int l, int r) {
//            if(begin > end)
//                return;
//            int tmp = arr[begin];
//            int i = begin;
//            int j = end;
//            while(i != j){
//                while(arr[j] >= tmp && j > i)
//                    j--;
//                while(arr[i] <= tmp && j > i)
//                    i++;
//                if(j > i){
//                    int t = arr[i];
//                    arr[i] = arr[j];
//                    arr[j] = t;
//                }
//            }
//            arr[begin] = arr[i];
//            arr[i] = tmp;
//            Quick_Sort(arr, begin, i-1);
//            Quick_Sort(arr, i+1, end);
//
//        if (l >= r - 1) {
//            return;
//        }
//        int basic = data[l];
//        // 计算断点m, n
//        int i = l, m = l, n = r;
//        int temp;
//        while (i < n) {
//            if (data[i] < basic) {
//                temp = data[i++];
//                data[i++] = data[m++];
//                data[m++] = temp;
//            } else if (data[i] > basic) {
//                temp = data[i];
//                data[i] = data[--n];
//                data[--n] = temp;
//            } else {
//                ++i;
//            }
//        }
//        quickSort(data, l, m);
//        quickSort(data, n, r);
//    }
}
